package org.example.everyday;

import java.util.HashMap;
import java.util.Map;

/**
 * <p>
 * Description:TODO 详细描述
 * <p>
 * <p>
 *
 * @author anlu
 * @date 2022/5/22 0022 9:43
 */
public class Lc464 {
    Map<Integer,Boolean> memo = new HashMap<Integer, Boolean>();
    public static void main(String[] args) {
        Lc464 lc464 = new Lc464();
        int maxChoosableInteger = 10, desiredTotal = 6;
        boolean res = lc464.canIWin(maxChoosableInteger,desiredTotal);
        System.out.println(res);

    }
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if((1 + maxChoosableInteger) * (maxChoosableInteger)/2 < desiredTotal){
            return false;
        }

        return dfs(maxChoosableInteger,0,desiredTotal,0);
    }

    private boolean dfs(int maxChoosableInteger, int usedNumbers, int desiredTotal, int currentToal) {
        if(!memo.containsKey(usedNumbers)){
            boolean res = false;
            for (int i = 0; i < maxChoosableInteger; i++) {
                if(((usedNumbers >> i) & 1) == 0){
                    if((i + 1 + currentToal >= desiredTotal) ){

                        res = true;
                        break;
                    }
                    if(!dfs(maxChoosableInteger,usedNumbers|(1<<i),desiredTotal,currentToal+i+1)){
                        res = true;
                        break;
                    }
                }
            }
            memo.put(usedNumbers,res);
            System.out.println("usedNumbers："+usedNumbers+";currentToal:"+currentToal);
        }
        return memo.get(usedNumbers);
    }


}
